package com.alex.space.commons.dynamic;

/**
 * 动态规划
 *
 * @author Alex
 * Created by Alex on 2018/3/5.
 */
public class DynamicUtils {

	public static void main(String[] args) {
		System.out.println("==LCS str1:abcdeght, str2:abecd, " + LCS("abcdeght", "abecd"));

		System.out.println("==LIS1 int:{1,2,5,4,8,3,9}, " + LIS1(new int[]{1, 2, 5, 4, 8, 3, 9}));

		System.out.println("==LIS2 int:{1,2,5,4,8,3,9}, " + LIS2(new int[]{1, 2, 5, 4, 8, 3, 9}));

		System.out.println("==Knapsack1 weight:{10,20,30,35},value:{60,100,120,150} " +
				Knapsack1(new int[]{10, 20, 30, 35}, new int[]{60, 100, 120, 150}, 60));

		System.out.println("==Knapsack2 weight:{10,20,30,35},value:{60,100,120,150} " +
				Knapsack2(new int[]{10, 20, 30, 35}, new int[]{60, 100, 120, 150}, 60));

		System.out.println("==Knapsack3 weight:{10,20,30,35},value:{60,100,120,150} " +
				Knapsack3(new int[]{10, 20, 30, 35}, new int[]{60, 100, 120, 150}, 60));

		System.out.println("==Knapsack4 weight:{10,20,30,35},value:{60,100,120,150},num:{1,1,1,1} " +
				Knapsack4(new int[]{10, 20, 30, 35}, new int[]{60, 100, 120, 150}, new int[]{1, 1, 1, 1}, 60));

		System.out.println("==Knapsack5 weight:{10,20,30,35},value:{60,100,120,150},num:{1,1,1,1} " +
				Knapsack5(new int[]{10, 20, 30, 35}, new int[]{60, 100, 120, 150}, new int[]{1, 1, 1, 1}, 60));
	}

	/**
	 * 最长公共子序列
	 * 一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列
	 */
	public static int LCS(String str1, String str2) {
		int[][] maxLen = new int[str1.length() + 1][str2.length() + 1];


		for (int i = 0; i <= str1.length(); i++) {
			for (int j = 0; j <= str2.length(); j++) {
				maxLen[i][j] = 0;
			}
		}

		for (int i = 1; i <= str1.length(); i++) {
			for (int j = 1; j <= str2.length(); j++) {
				if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
					maxLen[i][j] = maxLen[i - 1][j - 1] + 1;
				} else {
					maxLen[i][j] = maxLen[i][j - 1] > maxLen[i - 1][j] ? maxLen[i][j - 1] : maxLen[i - 1][j];
				}
			}
		}

		return maxLen[str1.length()][str2.length()];
	}

	/**
	 * 最长上升子序列
	 * 对于给定的序列，求出最长上升子序列的长度
	 */
	public static int LIS1(int[] src) {
		int[] maxLen = new int[src.length];

		for (int i = 0; i < maxLen.length; i++) {
			maxLen[i] = 1;
		}

		//每次求以第i个数为终点的最长上升子序列的长度
		for (int i = 1; i < src.length; i++) {
			//以第j个数为终点的最长上升子序列
			for (int j = 0; j < i; j++) {
				if (src[i] > src[j]) {
					maxLen[i] = maxLen[i] > maxLen[j] + 1 ? maxLen[i] : (maxLen[j] + 1);
				}
			}
		}

		int max = 1;
		for (int value : maxLen) {
			max = max > value ? max : value;
		}

		return max;
	}

	/**
	 * 最长上升子序列
	 * 对于给定的序列，求出最长上升子序列的长度
	 */
	public static int LIS2(int[] src) {
		int[] maxLen = new int[src.length];

		for (int i = 0; i < maxLen.length; i++) {
			maxLen[i] = 1;
		}

		for (int i = 0; i < maxLen.length; i++) {
			for (int j = i + 1; j < maxLen.length; j++) {
				if (src[i] < src[j]) {
					maxLen[j] = maxLen[j] > maxLen[i] + 1 ? maxLen[j] : (maxLen[i] + 1);
				}
			}
		}

		int max = 1;
		for (int value : maxLen) {
			max = max > value ? max : value;
		}

		return max;
	}

	/**
	 * 0-1 背包问题
	 *
	 * @param weight 重量
	 * @param value  价值
	 * @param volume 背包容量
	 */
	public static int Knapsack1(int[] weight, int[] value, int volume) {
		if (weight.length != value.length) {
			return 0;
		}

		int num = weight.length;
		int[][] dp = new int[num][volume + 1];

		//从1开始有讲究的因为涉及到dp[i-1][j],从0开始会越界
		for (int i = 0; i < num; i++) {
			//判断每个物品能否放进
			for (int j = 1; j <= volume; j++) {
				if (j >= weight[i]) {
					dp[i][j] = i == 0 ? value[i] : max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
				} else {
					dp[i][j] = i == 0 ? 0 : dp[i - 1][j];
				}

			}

		}
		return dp[num - 1][volume];
	}

	/**
	 * 0-1 背包问题
	 *
	 * @param weight 重量
	 * @param value  价值
	 * @param volume 背包容量
	 */
	public static int Knapsack2(int[] weight, int[] value, int volume) {
		if (weight.length != value.length) {
			return 0;
		}

		int num = weight.length;
		int[] dp = new int[volume + 1];

		for (int i = 0; i < num; i++) {
			//这里这个循环定死，不能反,反了就是完全背包
			for (int j = volume; j >= weight[i]; j--) {
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}

		return dp[volume];
	}

	/**
	 * 完全 背包问题
	 *
	 * @param weight 重量
	 * @param value  价值
	 * @param volume 背包容量
	 */
	public static int Knapsack3(int[] weight, int[] value, int volume) {
		if (weight.length != value.length) {
			return 0;
		}

		int num = weight.length;
		int[] dp = new int[volume + 1];

		for (int i = 0; i < num; i++) {
			for (int j = weight[i]; j <= volume; j++) {
				dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
			}
		}

		return dp[volume];
	}

	/**
	 * 完全 背包问题
	 *
	 * @param weight 重量
	 * @param value  价值
	 * @param count  数量
	 * @param volume 背包容量
	 */
	public static int Knapsack4(int[] weight, int[] value, int[] count, int volume) {
		if (weight.length != value.length || weight.length != count.length) {
			return 0;
		}

		int num = weight.length;
		int[] dp = new int[volume + 1];

		for (int i = 0; i < num; i++) {
			//其实就是把这类物品展开，调用num[i]次01背包代码
			for (int k = 0; k < count[i]; k++) {
				//这里这个循环定死，不能反,反了就是完全背包
				for (int j = volume; j >= weight[i]; j--) {
					dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
				}
			}
		}

		return dp[volume];
	}

	/**
	 * 完全 背包问题
	 *
	 * @param weight 重量
	 * @param value  价值
	 * @param count  数量
	 * @param volume 背包容量
	 */
	public static int Knapsack5(int[] weight, int[] value, int[] count, int volume) {
		if (weight.length != value.length || weight.length != count.length) {
			return 0;
		}

		int num = weight.length;
		int[] dp = new int[volume + 1];

		for (int i = 0; i < num; i++) {
			//遍历每种物品
			if (count[i] * weight[i] > volume) {
				//如果全装进去已经超了重量，相当于这个物品就是无限的
				//因为是取不光的。那么就用完全背包去套
				Complete_Pack(dp, value[i], weight[i], volume);
			} else {
				int k = 1;
				//遍历每种取法
				//这里用到是二进制思想，降低了复杂度
				//为什么呢，因为他取的1,2,4,8...个该物品，打包成一个大型的该物品
				//这样足够凑出了从0-k个该物品取法
				//把复杂度从k变成了logk
				//如k=11，则有1,2,4,4，足够凑出0-11个该物品的取法
				while (k < count[i]) {
					ZeroOne_Pack(dp, k * value[i], k * weight[i], volume);
					count[i] -= k;
					k <<= 1;
				}
				ZeroOne_Pack(dp, count[i] * value[i], count[i] * weight[i], volume);

			}

		}
		return dp[volume];
	}

	public static void ZeroOne_Pack(int[] dp, int value, int weight, int volume) {
		for (int j = volume; j >= weight; j--) {
			dp[j] = max(dp[j], dp[j - weight] + value);
		}
	}

	public static void Complete_Pack(int[] dp, int value, int weight, int volume) {
		for (int j = volume; j >= weight; j--) {
			dp[j] = max(dp[j], dp[j - weight] + value);
		}
	}

	private static int max(int a, int b) {
		return a > b ? a : b;
	}
}
